#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.5节：整数倍问题
#        给定一个自然数N<10000，和一个十进制数字集合X=｛x1, x2, ..., xm｝ 0<m<=10, 找出N的最小正整数倍，
#        使得该倍数中包含的数字都在X中。若在正整倍数的位数500位以内无法找到，则输出失败信息
#  
################################################################
import numpy as np
from pprint import pprint
from collections import deque, namedtuple

MAX_NODE = 10000  # N<9999
MAX_LEVEL = 500  # 最大500个十进制位，树的深度最大500

nodetp = namedtuple('nodetp', ['digit', 'res', 'parent'])

def get_answer(q): # 此种实现方法很低效
    d = q.pop()
    v = [str(d.digit)]
    while q and d.parent:
        t = q.pop()
        if d.parent == t :
            v.append(str(t.digit))
            d = t
    return v

def trySearch(q, setx, num, existres, qout):
    ''' q中已经放置了一层的节点，把这一层节点处理完之后退出，处理过程中会增加下一层节点的内容。
        如果处理过程中，找到了num的整数倍，则停止，输出结果，并返回true
    '''
    l = len(q)
    for _ in range(l):
        item = q.popleft()
        for x in sorted(setx):
            r = (item.res * 10 + x) % num
            if existres[r] : continue
            existres[r] = True
            q.append(nodetp(x, r, item))
            qout.append(nodetp(x, r, item))
            if r == 0:
                return True
    return False # 扩展完下一层，并没有num的整数倍

def search_leastmultiple(num, setx):
    existres = [False] * MAX_NODE
    queue = deque([nodetp(0, 0, None)]) # 准备第一层
    qout  = deque()  # 用来存放使用过的节点，为将来输出答案使用
    ok = False
    for level in range(MAX_LEVEL):
        #print '='*40
        #for i in queue: print i
        #print '-'*80
        if trySearch(queue, setx, num, existres, qout) :
            ok = True
            return ok, qout
    return ok, None

if __name__ == '__main__':
    setx = (2, 5, 4)
    num = 15
    ok, q = search_leastmultiple(num, setx)
    if ok:
        print ''.join(reversed(get_answer(q)))

    setx = (9, 8, 7, 5)
    num = 4984
    ok, q = search_leastmultiple(num, setx)
    if ok:
        print ''.join(reversed(get_answer(q)))

    setx = (1,2,3,4,5,6,7)
    num = 9999
    ok, q = search_leastmultiple(num, setx)
    if ok:
        print ''.join(reversed(get_answer(q)))

    setx = (1,)
    num = 89
    ok, q = search_leastmultiple(num, setx)
    if ok:
        print ''.join(reversed(get_answer(q)))
